In mainstream image encoding, each pixel value of the encoding target is predicted using previously-decoded former or upper pixels to obtain a prediction residual which is then encoded.
In such a prediction encoding method, when encoding a target pixel to be encoded (called “p”), a predicted value for p is generated using the fact that previously-decoded peripheral pixels (e.g., Inw, In, Ine, and Iw in FIG. 14) have generally high correlation with p. Thus such peripheral pixels are actually used. In the equations below, the predicted value for p is called p′. In the step that follows, a prediction error p-p′ is subjected to entropy encoding.
For example, Lossless Mode in JPEG (see Non-Patent Document 1) has seven types of predictors, and one selected from among them is used for predicting and encoding a pixel value.
In an example called an “average prediction” as one of the methods in the JPEG predictors, prediction is performed by computing an average between In and Iw as follows:x′=(In+Iw)/2  Formula (1)
There are also six other prediction methods (in addition to the above) which include:x′=In+Iw−Inw plane prediction  Formula (2)x′=In previous value prediction  Formula (3)x′=Inw+(In−Iw)/2 complex prediction  Formula (4)
JPEG-LS (see Non-Patent Document 2) having a higher level of efficiency than JPEG employs a slightly more complicated prediction method called “MED prediction” as shown below.
if Inw max (Iw, In) then
                x′=min (Iw, In)else if Inw min (Iw, In) then        x′=max (Iw, In)else        x′=Iw+In−Inwwhere max (x, y) is a function that returns one of x and y, whichever is larger, and min (x, y) is a function that returns one of x and y, whichever is smaller.        
In addition, a method which defines a weighted average between peripheral pixels to be a predicted value is generally known. In a simplified method, the weight of each peripheral pixel may be computed by means of a least-square method for each image, or coefficient optimization for minimizing the relevant amount of code may be performed (see Non-Patent Document 3).
Additionally, although it does not belong to prediction encoding, Non-Patent Document 4 discloses encoding parameter optimization for image or video encoding, which employs a genetic algorithm (GA), where a “template” for generating a context which is used for encoding a binary image is modified using a genetic algorithm, thereby improving efficiency. That is, the template is treated as a parameter, and a fixed encoding procedure is used.
As a similar method relating directionality, Non-Patent Document 5 discloses using a genetic algorithm for dynamically changing a divided shape of a unit area to be encoded, thereby improving the relevant efficiency. Similar to the template in Non-Patent Document 4, the encoding procedure is fixed also in this case.